/*
 * @lc app=leetcode.cn id=77 lang=cpp
 *
 * [77] 组合
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<int>> ans;
    void dfs(vector<int> res, int start, const int k, const int n)
    {
        if (k == res.size())
        {
            ans.push_back(res);
            return;
        }
        if (n - start + 1 + res.size() < k)
            return;
        {
            res.push_back(start);
            dfs(res, start + 1, k, n);
            res.erase(res.end() - 1);
            dfs(res, start + 1, k, n);
        }
        return;
    }
    vector<vector<int>> combine(int n, int k)
    {
        vector<int> res;
        dfs(res, 1, k, n);
        return ans;
    }
};

// int main()
// {
//     Solution().combine(4, 2);
//     return 0;
// }
// @lc code=end
